10. Transposition Tables

Transposition tables (often referred to as hash tables) are used for storing chess positions during the search to avoid re-searching positions that can be reached via several different move sequences. This can speed up the search dramatically, particularly in the endgame.

The famous Lasker position shown below is one of the most extreme examples:
 

White wins by the obscure move Ka1-b1!! rather than the more intuitive Ka1-b2 which merely leads to a draw. The reason for this is far from obvious and requires a search depth of at least 20 ply. Without transposition tables, finding this move would take many hours or even days for a chess program, but with transposition tables Sigma Chess finds the solution in less than a second! The reason for this dramatic speedup of the search is that there are very few different positions reachable from the initial position, because all the pawns are locked.

Sigma Chess stores 10 bytes per position, and actually maintains four separate transposition tables; two for each side. The larger the transposition tables, the more positions can be stored. However, even small tables (e.g. 320 Kb) give significant speedups. Very large transposition tables (e.g. 40 Mb or more) are not recommended on slow machines or during blitz games, because the tables have to be reset before starting the search and this can become quite time consuming. Additionally large transposition tables actually decreases the number of moves per second, because Sigma Chess then won't be able to use the processor cache properly. 640 Kb transposition tables is actually a very good setting except in the endgame.

The minimal transposition table size supported by Sigma Chess is 80 Kb (about 8.000 positions); the remaining sizes are achieved through ìsuccessive doublingî - i.e. 160 Kb, 320 Kb, 640 Kb, 1.25 Mb e.t.c - up to a maximum of 80 Mb. The absolute minimum amount of memory needed to run Sigma Chess is 3 MB (or 5 Mb if the 3D board is to be used). In the Memory "sheet" of the Preferences dialog, a certain amount of memory is reserved for general use, such as opening games, libraries, game collections etc. The remaining memory is assigned to the transposition tables. Since Sigma Chess supports mulitple engine "instances" running at the same time, the transposition table memory has to be divided between each engine. This is done in the Transposition Tables "sheet" in the Preferences dialog, where you can specify the maximum transposition table size for each engine. If you rarely run more than one engine at a time, you might want to assign most the available memory to the "first" engine.

Using transposition tables has one minor drawback: They are not 100 % fool proof. To be of any use, it must be possible to look up positions quickly and efficiently. This is achieved through so-called hash keys, which serve as indices in the transposition tables. But these keys are not unique and thus two different positions may ìhashî into the same table entry. However, for the hash keys to be unique they would have to be very large and therefore useless, and consequently there is a theoretical possibility that the program will sometimes retrieve incorrect information from the tables. In practical play, however, the probabililty is very low and the risk therefore worth taking because of the huge reductions in search time.

Sigma Chess will normally use transposition tables when solving mate problems. In case the program should fail finding a mate, you should turn off the transposition tables and try again. If this still has no effect, then there are no solutions!